package com.ly.algorithm.offerpointer;

import java.util.Arrays;

/**
 * @Classname Offer13
 * @Description
 *
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
 * 也不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，
 * 因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 2：
 *
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 *
 *
 * @Date 2021/1/17 21:20
 * @Author 冷心影翼
 */
public class Offer13 {

    public static void main(String[] args) {
        Solution13 solution13 = new Solution13();
//        System.out.println(solution13.movingCount(3, 1, 0));
        System.out.println(solution13.movingCountByDp(16, 8, 4));
    }
}


class Solution13 {

    private boolean[][] visited;

    private int ans;

    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        dfs(m,n,k,0,0);
        return ans;
    }

    public int movingCountByDp(int m, int n, int k) {
        visited = new boolean[m][n];
        ans = 1;
        visited[0][0] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if((i == 0 && j == 0) || calc(i,j)>k) {
                    continue;
                }
                if((i>0 && visited [i-1][j]) || (j>0 && visited[i][j-1])) {
                    visited [i][j] = true;
                    ans += 1;
                }else {
                    visited [i][j] = false;
                }
            }
        }
        return ans;
    }

    public int  calc(int i,int j) {
        int calc = 0;
        String s = i+""+j;
        for (int l = 0; l < s.length() ; l++) {
            calc = calc + (s.charAt(l)-'0');
        }
        return calc;
    }

    public void dfs(int m,int n,int k,int i,int j) {

        visited[i][j] = true;
        String s = i+""+j;
        int calc = 0;
        for (int l = 0; l < s.length() ; l++) {
            calc = calc + (s.charAt(l)-'0');
        }
        if(calc<=k) {
            ans++;
//            //上
//            if(i>0 && !visited[i-1][j]) {
//                dfs(m,n,k,i-1,j);
//            }
            //下
            if(i<m-1 && !visited[i+1][j]) {
                dfs(m,n,k,i+1,j);
            }
//            //左
//            if(j>0 && !visited[i][j-1]) {
//                dfs(m,n,k,i,j-1);
//            }
            //右
            if(j<n-1 && !visited[i][j+1]) {
                dfs(m,n,k,i,j+1);
            }
        }
    }
}